On the enumeration of maximal infinitely-generated classes of 01-functions in three-valued logic 

Sergey S. Marchenkov, Doctor of physical and mathematical sciences, professor, professor of the sub-department of mathematical cybernetics, Lomonosov Moscow State University (1 Leninskiye gory street, Moscow, Russia), E-mail: ssmarchen@yandex.ru 

519.716 

10.21685/2072-3040-2021-3-1 

Background. The superposition operation is the main operation in the study of multivalued logic functions. On the basis of this operation, classifications of multivalued logic functions are defined, which allow to solve important problems of expressiveness and completeness. However, if these problems have long been solved for Boolean functions (functions of two-valued logic), then, for example, for functions of k-valued logic (for k ≥ 3 ), the problem of describing all closed classes seems to have no satisfactory solution – in this case, the number of closed classes is continuous. In this connection, research on closed (with respect to the superposition operation) classes of functions of k-valued logic develops in the direction of describing various fragments of the lattice of closed classes: maximum and minimum classes, upper and lower cones, finite and countable intervals defined by meaningful classes, etc. One of the tasks of this direction, set by S. V. Yablonsky in the early 1980s, is to describe all maximal infinitely generated classes of a lattice of closed classes. In 1986, E. A. Mikheeva and G. Tardosh found examples of such maximal classes: E.A. Mikheeva for any k ≥ 3 , G. Tardosh for k = 8 . The ideas of Tardosh were further developed by O.S. Dudakova. However, for fixed k, it has not yet been possible to determine the series of maximal infinitely-generated classes. In 2019, the author published an article where 4 maximal infinitely-generated classes Π1 −Π4 are defined in threevalued logic, which consist of functions that take only the values 0 and 1 (the same classes can be defined for functions that take the values 0,2 and 1,2).Thus, a series of 12 maximal infinitely-generated classes appeared. There is every reason to believe that the classes Π1 −Π4 exhaust all maximal infinitely-generated classes of 01-functions. This fact can be proved by the following scheme. First, for each class Πi , you should define all the “simplest” functions from two or three variables that are obtained by superpositions from an arbitrary function that does not belong to the class Πi . Then it is necessary to iterate through all possible fours of the "simplest" functions and, using known sufficient conditions of finite generatability, to establish the finite generatability of closed classes containing the selected fours of functions. Materials and methods. The constructions and proofs use the methods of the functional systems theory. Results and conclusions. We consider a class Π of functions of three-digit logic that accept only the values 0 and 1. In the classroom Π there are 4 infinitely-generated classes Π1 −Π4 that have the maximality property: every closed class of Π that contains any of the classes Π1 −Π4 in its own way is finitelygenerated. For each class Πi and an arbitrary function f that does not belong to Πi and essentially depends on at least two variables, all “simplest” functions of two or three variables that are obtained by superpositions of the function f and that are not included in the class Πi are defined. In the future, all these functions are supposed to be used to prove that in the class Πi all maximal infinitely-generated classes are exhausted by the classes Π1 −Π4 . Such proof should roughly consist in the analysis of several thousand fours, consisting of the obtained “simplest” function. 

infinite-generated classes, 01-functions in ternary logic, theory of functional systems 

1. Post E.L. Introduction to a general theory of elementary propositions. Amer. J. Math. 1921;43(4):163–185.
2. Post E.L. Two-valued iterative systems of mathematical logic. Annals of Math. Studies. 1941;5:1–122.
3. Marchenkov S.S. Zamknutye klassy bulevykh funktsiy = Closed classes of Boolean functions. Moscow: Fizmatlit, 2000:126. (In Russ.)
4. Marchenkov S.S. Osnovy teorii bulevykh funktsiy = Fundamentals of the theory of Boolean functions. Moscow: Fizmatlit, 2014:135. (In Russ.)
5. Yanov Yu.I., Muchnik A.A. On the existence of k-valued closed classes without a basis. Doklady Akademii nauk SSSR = Reports of the Academy of Sciences of USSR. 1959;127(1):44–46. (In Russ.)
6. Mikheeva E.A. On the existence in k-valued logic of maximal classes without a finite basis. Doklady Akademii nauk SSSR = Reports of the Academy of Sciences of USSR. 1986;287(1):49–52. (In Russ.)
7. Mikheeva E.A. Construction in maximal classes without finite bases. Diskretnaya matematika = Discrete Math. 1998;10(2):137–159. (In Russ.)
8. Tardos G. A not finitely generated clone of monotone operations. Order. 1986;3:211–218.
9. Dudakova O.S. On a family of pre-field classes of functions of k-valued logic that do not have a finite basis. Vestnik Moskovskogo universiteta. Seriya 1: Matematika. Mekhanika = Bulletin of Moscow University. Series 1: Mathematics. Mechanics. 2006;(2):29–32. (In Russ.)
10. Marchenkov S.S. Finitely and infinitely generated classes of 01-functions of threevalued logic. Matematicheskie voprosy kibernetiki = Mathematical issues in cybernetics. 2019;(19):21–36. (In Russ.)